﻿#include<iostream>
using namespace std;

void print(int a[], int n)	//输出函数						{
{for (int i = 0; i < n; i++)
{
	cout << a[i] << " ";
}
cout << endl;
}

int Partition(int a[], int s, int t)
{
	int i = s, j = t;
	int tmp = a[s];
	while (i != j) {
		while (j > i && a[j] >= tmp)
		{
			j--;
		}
		a[i] = a[j];
		while (i < j && a[i] <= tmp)
		{
			i++;
		}
		a[j] = a[i];
	}
	a[i] = tmp;
	return i;

}
void QuickSort(int a[], int s, int t)	//快速排序

{
	if (s < t) {
		int i = Partition(a, s, t);
		QuickSort(a, s, i - 1);
		QuickSort(a, i + 1, t);
	}
}
void Bubblesort(int a[], int len)//冒泡排序

{
	for (int i = 0; i < len - 1; i++)
	{
		for (int j = 0; j < len - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
}

void swap(int a[], int i, int j)//交换函数

{
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}
void simpleChooseSort(int a[], int aLength)//简单选择排序
{
	int i, j, min;
	for (i = 0; i < aLength; i++) {
		min = i;
		for (j = i + 1; j < aLength; j++) {
			if (a[min] < a[j]) {
				min = j;
			}
		}
		if (i != min) {
			swap(a, i, min);
		}
	}
}
void insertsort(int a[], int n)
{/*直接插入排序*/
	int i, j, k;
	for (i = 1; i < n; i++)
	{
		k = a[i];
		j = i - 1;
		while (k < a[j]) {
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = k;
	}

}
void shell_sort(int NUM[], const int start, const int end)
{
	int increment = end - start + 1;
	int temp{ 0 };
	do {
		increment = increment / 3 + 1;
		for (int i = start + increment; i <= end; ++i) {
			if (NUM[i - increment] > NUM[i]) {
				temp = NUM[i];
				int j = i - increment;
				do {
					NUM[j + increment] = NUM[j];
					j -= increment;
				} while (j >= start && NUM[j] > temp);
				NUM[j + increment] = temp; 
			}
		}
	} while (increment > 1);

}


void three_max(int a[], int i, int size) //堆调整
{
	if (i < size)
	{
		int left = 2 * i + 1;
		int right = 2 * i + 2;
		int largest = i;
		if (left < size)
		{
			if (a[largest] < a[left])
			{
				largest = left;
			}
		}
		if (right < size)
		{
			if (a[largest] < a[right])
			{
				largest = right;
			}
		}
		if (largest != i)
		{
			int temp = a[largest];
			a[largest] = a[i];
			a[i] = temp;
			three_max(a, largest, size);
		}
	}
}void heap_l(int a[], int size) //建堆
{
	for (int i = size - 1; i >= 0; i--)
	{
		three_max(a, i, size);
	}
}
void heap_s(int a[], int size)//递归建堆 
{
	for (int i = size - 1; i >= 0; i--)
	{
		heap_l(a, i + 1);
		int temp = a[0];
		a[0] = a[i];
		a[i] = temp;
	}
}

int main()
{
	int n = 10;
	int a[10];
	cout << "输入十个数字" << endl;
	for (int i = 0; i < 10; i++)
	{
		cin >> a[i];
	}
	printf("输入的是个数字为：");
	print(a, n);
	QuickSort(a, 0, n - 1);
	printf("快速排序：");
	print(a, n);
	Bubblesort(a, n);
	printf("冒泡排序：");
	print(a, n);
	simpleChooseSort(a, n);
	printf("简单选择排序：");
	print(a, n);
	printf("直接插入排序：");
	insertsort(a, n);
	print(a, n);
	printf("希尔排序：");
	shell_sort(a, 1, n - 1);
	print(a, n);
	printf("堆排序："); 
	heap_l(a, n);
	heap_s(a, n);
	print(a, n);
	system("pause");
}

